In this protocol, we propose to extend observations made during a previous clinical trial in which patients with resected melanoma that were immunized with a peptide vaccine demonstrated augmented T cell immunity specifically directed toward the immunizing antigen. In that trial, as in several others in which patients with melanoma were immunized with epitope peptides, incomplete Freund's adjuvant (IFA) was used and the duration of immunization schedules was brief. Important questions that remain to be resolved in the cancer vaccine field include the optimal dose, schedule and adjuvant combination for immunization. In the current trial, we will perform a two center randomized phase II trial in which HLA-A2+ patients with resected stages IIA and IIB melanoma will be vaccinated with one of three vaccine regimens. Arm A will consist of eight paired vaccinations with tyrosinase plus IFA and gp 100 plus IFA over increasing intervals of time as the "standard" regimen. Patients in Arb B will receive the some regimen as in Arm A but with a block co-polymer adjuvant CRL 1005 emusified with the peptide/IFA combination. Patients in Arm C will receive GM-CSF injected subcutaneously proximal to the vaccination site the day of and for four days after vaccination with the same regimen as Arm A. The principal endpoint of the study to be conducted as a collaboration between the University of Michigan andUSC/Norris Cancer Center will be the immu e response to the antigen peptides and a quantitative comparison of immune reaponses on each arm. Skin testing with the peptides, cytokine release by peptide stimulated CTL grown from peripheral blood, and precursor CTL frequency estimated from ELISPOT assays prior to and after vaccinations will be used to measure immune responses. Assessment of T cell receptor zeta chain expression will also be performed. The results of this trial will be used to design the experimental arm of future randomized phase III trials in patients with resected high risk melanoma. Specific GCRC support is being requested for the performance of pretreatment skin testing and plasmapheresis before and after vaccination on a total of 40 patients over two years.